/* Time-stamp: <2010-10-24 21:38:25 xinhaoyuan> */
/* Privide debugging feature(monitor) for EKOS */
/* This file is original from the assignment JOS */

#include "kernel.h"

struct eipdebuginfo_t {
     const char *eip_file;		// Source code filename for EIP
     int eip_line;			// Source code linenumber for EIP

     const char *eip_fn_name;	// Name of function containing EIP
     //  - Note: not null terminated!
     int eip_fn_namelen;		// Length of function name
     uintptr_t eip_fn_addr;		// Address of start of function
     int eip_fn_narg;		// Number of function arguments
};

// stab_binsearch(stabs, region_left, region_right, type, addr)
//
//	Some stab types are arranged in increasing order by instruction
//	address.  For example, N_FUN stabs (stab entries with n_type ==
//	N_FUN), which mark functions, and N_SO stabs, which mark source files.
//
//	Given an instruction address, this function finds the single stab
//	entry of type 'type' that contains that address.
//
//	The search takes place within the range [*region_left, *region_right].
//	Thus, to search an entire set of N stabs, you might do:
//
//		left = 0;
//		right = N - 1;     /* rightmost stab */
//		stab_binsearch(stabs, &left, &right, type, addr);
//
//	The search modifies *region_left and *region_right to bracket the
//	'addr'.  *region_left points to the matching stab that contains
//	'addr', and *region_right points just before the next stab.  If
//	*region_left > *region_right, then 'addr' is not contained in any
//	matching stab.
//
//	For example, given these N_SO stabs:
//		Index  Type   Address
//		0      SO     f0100000
//		13     SO     f0100040
//		117    SO     f0100176
//		118    SO     f0100178
//		555    SO     f0100652
//		556    SO     f0100654
//		657    SO     f0100849
//	this code:
//		left = 0, right = 657;
//		stab_binsearch(stabs, &left, &right, N_SO, 0xf0100184);
//	will exit setting left = 118, right = 554.
//
static void
stab_binsearch(const struct stab_t *stabs, int *region_left, int *region_right,
			   int type, uintptr_t addr)
{
     int l = *region_left, r = *region_right, any_matches = 0;
	
     while (l <= r) {
		  int true_m = (l + r) / 2, m = true_m;
		
		  // search for earliest stab with right type
		  while (m >= l && stabs[m].n_type != type)
			   m--;
		  if (m < l) {	// no match in [l, m]
			   l = true_m + 1;
			   continue;
		  }

		  // actual binary search
		  any_matches = 1;
		  if (stabs[m].n_value < addr) {
			   *region_left = m;
			   l = true_m + 1;
		  } else if (stabs[m].n_value > addr) {
			   *region_right = m - 1;
			   r = m - 1;
		  } else {
			   // exact match for 'addr', but continue loop to find
			   // *region_right
			   *region_left = m;
			   l = m;
			   addr++;
		  }
     }

     if (!any_matches)
		  *region_right = *region_left - 1;
     else {
		  // find rightmost region containing 'addr'
		  for (l = *region_right;
			   l > *region_left && stabs[l].n_type != type;
			   l--)
			   /* do nothing */;
		  *region_left = l;
     }
}


// debuginfo_eip(addr, info)
//
//	Fill in the 'info' structure with information about the specified
//	instruction address, 'addr'.  Returns 0 if information was found, and
//	negative if not.  But even if it returns negative it has stored some
//	information into '*info'.
//
static int
debuginfo_eip(uintptr_t addr, struct eipdebuginfo_t *info)
{
     const struct stab_t *stabs, *stab_end;
     const char *stabstr, *stabstr_end;
     int lfile, rfile, lfun, rfun, lline, rline;

     // Initialize *info
     info->eip_file = "<unknown>";
     info->eip_line = 0;
     info->eip_fn_name = "<unknown>";
     info->eip_fn_namelen = 9;
     info->eip_fn_addr = addr;
     info->eip_fn_narg = 0;

     // Find the relevant set of stabs
     if (addr >= ULIM) {
		  stabs = __STAB_BEGIN__;
		  stab_end = __STAB_END__;
		  stabstr = __STABSTR_BEGIN__;
		  stabstr_end = __STABSTR_END__;
     } else {
		  // Can't search for user-level addresses yet!
		  return -1;
     }

     // String table validity checks
     if (stabstr_end <= stabstr || stabstr_end[-1] != 0)
		  return -1;

     // Now we find the right stabs that define the function containing
     // 'eip'.  First, we find the basic source file containing 'eip'.
     // Then, we look in that source file for the function.  Then we look
     // for the line number.
	
     // Search the entire set of stabs for the source file (type N_SO).
     lfile = 0;
     rfile = (stab_end - stabs) - 1;
     stab_binsearch(stabs, &lfile, &rfile, N_SO, addr);
     if (lfile == 0)
		  return -1;

     // Search within that file's stabs for the function definition
     // (N_FUN).
     lfun = lfile;
     rfun = rfile;
     stab_binsearch(stabs, &lfun, &rfun, N_FUN, addr);

     if (lfun <= rfun) {
		  // stabs[lfun] points to the function name
		  // in the string table, but check bounds just in case.
		  if (stabs[lfun].n_strx < stabstr_end - stabstr)
			   info->eip_fn_name = stabstr + stabs[lfun].n_strx;
		  info->eip_fn_addr = stabs[lfun].n_value;
		  addr -= info->eip_fn_addr;
		  // Search within the function definition for the line number.
		  lline = lfun;
		  rline = rfun;
     } else {
		  // Couldn't find function stab!  Maybe we're in an assembly
		  // file.  Search the whole file for the line number.
		  info->eip_fn_addr = addr;
		  lline = lfile;
		  rline = rfile;
     }
     // Ignore stuff after the colon.
     info->eip_fn_namelen = strfind(info->eip_fn_name, ':') - info->eip_fn_name;

	
     // Search within [lline, rline] for the line number stab.
     // If found, set info->eip_line to the right line number.
     // If not found, return -1.
     //
     // Hint:
     //	There's a particular stabs type used for line numbers.
     //	Look at the STABS documentation and <inc/stab.h> to find
     //	which one.
     // Your code here.

     stab_binsearch(stabs, &lline, &rline, N_SLINE, addr);
     if (lline <= rline)
     {
		  rline = lline;
		  info->eip_line = stabs[lline].n_desc;
     }
     else
     {
		  info->eip_line = -1;
		  lline = lfile;
		  rline = rfile;
     }
	
     // Search backwards from the line number for the relevant filename
     // stab.
     // We can't just use the "lfile" stab because inlined functions
     // can interpolate code from a different file!
     // Such included source files use the N_SOL stab type.
     while (lline >= lfile
			&& stabs[lline].n_type != N_SOL
			&& (stabs[lline].n_type != N_SO || !stabs[lline].n_value))
		  lline--;
     if (lline >= lfile && stabs[lline].n_strx < stabstr_end - stabstr)
		  info->eip_file = stabstr + stabs[lline].n_strx;


     // Set eip_fn_narg to the number of arguments taken by the function,
     // or 0 if there was no containing function.
     // Your code here.

     info->eip_fn_narg = 0;
     if (info->eip_line != -1)
     {
		  ++lfun;
		  while (lfun < rfile
				 && stabs[lfun].n_type == N_PSYM
			   )
		  {
			   ++lfun;
			   ++info->eip_fn_narg;
		  }
     }
	
     return 0;
}

#define CMDBUF_SIZE	80	// enough for one VGA text line

struct command_t {
     const char *name;
     const char *desc;
     // return -1 to force monitor to exit
     int (*func)(int argc, char** argv, struct trapframe_t* tf);
};

static int mon_help(int argc, char** argv, struct trapframe_t *tf);
static int mon_kerninfo(int argc, char** argv, struct trapframe_t *tf);
static int mon_backtrace(int argc, char** argv, struct trapframe_t *tf);
static int mon_mapping(int argc, char **argv, struct trapframe_t *tf);

static struct command_t commands[] = {
     { "help", "Display this list of commands", mon_help },
     { "kerninfo", "Display information about the kernel", mon_kerninfo },
     { "bt", "Display information of stack", mon_backtrace},
     { "backtrace", "Display information of stack", mon_backtrace},
	 { "mapping", "Display information about current linear address mapping", mon_mapping},
};

#define NCOMMANDS (sizeof(commands)/sizeof(commands[0]))

/***** Implementations of basic kernel monitor commands *****/

static int
mon_help(int argc, char **argv, struct trapframe_t *tf)
{
     int i;

     for (i = 0; i < NCOMMANDS; i++)
		  cprintf("%s - %s\n", commands[i].name, commands[i].desc);
     return 0;
}

static int
mon_kerninfo(int argc, char **argv, struct trapframe_t *tf)
{
     cprintf("Special kernel symbols:\n");
     cprintf("  _start     %08x (virt)  %08x (phys)\n", _start,    _start - KBASE);
     cprintf("  _text      %08x (virt)  %08x (phys)\n", _text,     _text - KBASE);
     cprintf("  _text_end  %08x (virt)  %08x (phys)\n", _text_end, _text_end - KBASE);
     cprintf("  _bss       %08x (virt)  %08x (phys)\n", _bss,      _bss - KBASE);
     cprintf("  _end       %08x (virt)  %08x (phys)\n", _end,      _end - KBASE);
     cprintf("Kernel executable memory footprint: %dKB\n",
			 (_end - _text + 1023)/1024);
     return 0;
}

static int
mon_backtrace(int argc, char **argv, struct trapframe_t *tf)
{
     uint32_t ebp, nebp;
     uint32_t eip = 0;
     struct eipdebuginfo_t debug_info;

     asm volatile("movl %%ebp, %0" : "=r" (ebp));

     cprintf("Stack backtrace:\n");
     /* cprintf("  ebp: %p\n", ebp); */

     while (1)
     {
		  asm volatile("movl 4(%0), %1" : "=r" (eip) : "r"(ebp));
		  asm volatile("movl (%0), %1"
					   : "=r" (nebp)
					   : "q" (ebp)
			   );
		  ebp = nebp;

		  /* break if the ptr down to user mode */
		  if (ebp < ULIM)
		  {
			   if (tf == NULL)
					break;
			   if ((ebp = tf->regs.ebp) < ULIM)
					break;
			   tf = NULL;
			   cprintf("============================================================\n");
		  }
	  
		  cprintf("  ebp: %p  eip: %p", ebp, eip);
	  
		  if (debuginfo_eip(eip, &debug_info) >= 0)
		  {
			   cprintf("  args[%d]", debug_info.eip_fn_narg);
			   int arg_idx;
			   uint32_t arg;
			   for (arg_idx = 0; arg_idx < debug_info.eip_fn_narg; ++ arg_idx)
			   {
			   		arg = *((uint32_t *)ebp + arg_idx + 2);
			   		cprintf(" %08x", arg);
			   }

			   cprintf("\n\t%s:%d: ", debug_info.eip_file, debug_info.eip_line, debug_info.eip_fn_narg);
	       
			   int i;
			   for (i = 0; i != debug_info.eip_fn_namelen; ++i)
					cputchar(debug_info.eip_fn_name[i]);

			   cprintf("+%d\n", eip - debug_info.eip_fn_addr);
		  }
		  else
		  {
			   // cprintf("%s : %d\n", debug_info.eip_file, debug_info.eip_line);
			   cprintf(" [debug info missing]\n");
		  }
     }

	 cprintf("============================================================\n");
	 cprintf("Trapframe(%08x):\n", tf);
	 cprintf("EIP: %08x\n", tf->eip);
     
     return 0;
}

static int
mon_mapping(int argc, char **argv, struct trapframe_t *tf)
{
	 if (argc == 1)
	 {
		  cprintf("usage: %s [addr1] [addr2] ...", argv[0]);
	 }
	 else
	 {
		  int i;
		  uintptr_t addr;
		  
		  for (i = 1; i < argc; ++ i)
		  {
			   char *str = argv[i];
			   if (parse_uint32(&str, &addr) != 0)
			   {
					cprintf("%s is not a vaild address\n", argv[i]);
			   }
			   else
			   {
					physaddr_t result = phys_addr((void *)addr);
					if (result == 0)
					{
						 cprintf("%08x is unavailable\n", addr);
					}
					else
					{
						 cprintf("%08x => %08x\n", addr, result);
					}
			   }
			   
		  }
	 }
	 
	 return 0;
}


/***** Kernel monitor command interpreter *****/

#define WHITESPACE "\t\r\n "
#define MAXARGS 16

static int
runcmd(char *buf, struct trapframe_t *tf)
{
     int argc;
     char *argv[MAXARGS];
     int i;

     // Parse the command buffer into whitespace-separated arguments
     argc = 0;
     argv[argc] = 0;
     while (1) {
		  // gobble whitespace
		  while (*buf && strchr(WHITESPACE, *buf))
			   *buf++ = 0;
		  if (*buf == 0)
			   break;

		  // save and scan past next arg
		  if (argc == MAXARGS-1) {
			   cprintf("Too many arguments (max %d)\n", MAXARGS);
			   return 0;
		  }
		  argv[argc++] = buf;
		  while (*buf && !strchr(WHITESPACE, *buf))
			   buf++;
     }
     argv[argc] = 0;

     // Lookup and invoke the command
     if (argc == 0)
		  return 0;
     for (i = 0; i < NCOMMANDS; i++) {
		  if (strcmp(argv[0], commands[i].name) == 0)
			   return commands[i].func(argc, argv, tf);
     }
     cprintf("Unknown command '%s'\n", argv[0]);
     return 0;
}

void
monitor(struct trapframe_t *tf)
{
     char *buf;

     cprintf("EKOS kernel monitor\n");
     cprintf("Type 'help' for a list of commands.\n");

     while (1) {
		  buf = readline("K> ");
	  
		  if (strcmp(buf, "quit") == 0) break;
	  
		  if (buf != NULL)
			   if (runcmd(buf, tf) < 0)
			   {
					break;
			   }
     }

     breakpoint();
}
